package by2019;


/**
 * LeetCode 69
 * 
 * @author CARRY ME HOME
 * @date 2019年9月27日 上午10:50:40
 */
public class X的平方根 {
	
	
	public static void main(String[] args) {
		long t = System.currentTimeMillis();
		System.out.println(mySqrt(2147395599));
		System.out.println(System.currentTimeMillis() - t);
	}

	public static  int mySqrt(int x) {
		 int min = 1;
			int max = x;
			
			if(x < 1)
				return 0;
			if(x == 1)
				return 1;
			
			while(true) {
				
				int m = (min + max)/2;
				
				if(m  <= (x/m) )
					min = m;
				else
					max = m;
				
				if(max == min)
					return max;
				
				if((max - min) == 1) {
					if(max * max == x)
						return max;
					return min;
				}
			}

		}
}
